package com.demo.algorithm.slidingWindow05;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * Author:       zhangshaoyang
 * Description:  LeetCode 第 438 题，Find All Anagrams in a String，难度 Medium
 * 给定一个字符串s和一个非空字符串p，找到s中所有是p的字母异位词的子串，返回这些子串的起始索引。
 * 字符串只包含小写英文字母，并且字符串s和 p的长度都不超过 20100。
 * 说明：
 * 字母异位词指字母相同，但排列不同的字符串。
 * 不考虑答案输出的顺序。
 * <p>
 * ⚠️注：相当于，输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。
 * <p>
 * 示例1:
 * 输入:
 * s: "cbaebabacd" p: "abc"
 * 输出:
 * [0, 6]
 * 解释:
 * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
 * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
 * <p>
 * 示例 2:
 * 输入:
 * s: "abab" p: "ab"
 * 输出:
 * [0, 1, 2]
 * 解释:
 * 起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
 * 起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
 * 起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * Date:         2021/6/10 4:18 下午
 */
public class AnagramsInString {

    private static LinkedList<Integer> findAnagrams(String s, String p) {
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();
        char[] chars = s.toCharArray();
        char[] charp = p.toCharArray();

        for (char c : charp) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;
        int valid = 0;
        LinkedList<Integer> indexs = new LinkedList<>();

        while (right < chars.length) {
            char c = chars[right];
            right++;
            //进行窗口内数据的一系列更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            //判断左侧窗口是否要收缩
            while (right - left == charp.length) {
                //在这里判断是否找到了合法的子串
                if (valid == need.size()) {
                    indexs.add(left);
                }
                char d = chars[left];
                left++;
                //进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        // 返回索引
        return indexs;
    }

    public static void main(String[] args) {
//        String s = "cbaebabacd", p = "abc";
        String s = "abab", p = "ab";
        System.out.println("findAnagrams(s, p) = " + findAnagrams(s, p));

    }

}
